home *** CD-ROM | disk | FTP | other *** search
/ Multimedia Plus / Multimedia Plus with ClearVue Version 10-94 (Knowledge Media Inc.).ISO / dos / viewers / wmorph10 / wmorph.doc < prev    next >
Encoding:
Text File  |  1993-08-22  |  10.0 KB  |  343 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.                          WMORPH - 2-D Morphing Program
  11.  
  12.                            Version 1.0  May 21, 1993
  13.  
  14.                          Lam Ka Po (cs_lamkp@stu.ust.hk)
  15.                        Wong Wing Kin (cs_wwkin@stu.ust.hk)
  16.  
  17.  
  18.  
  19.  
  20.  
  21.  
  22.  
  23.  
  24.  
  25. Objective
  26.  
  27.         This program WMORPH is a self-proposed project in our Computer
  28. Graphics course.  The aim of the project is to build a 2-D Morphing system
  29. running on PC.  User can input two 320x200 256-color GIF images files
  30. and specify corresponding points on the two images.  The system will
  31. produce a series of intermediate images showing the transition from the
  32. original image to the desired image.  The intermediate images are
  33. stored as 320x200 256-color GIF images file.
  34.  
  35.  
  36.  
  37.  
  38.  
  39.  
  40.  
  41.  
  42.  
  43.  
  44.  
  45.  
  46.  
  47.  
  48. 2-D Morphing
  49.     
  50.         Most of the techniques for 2-D morphing come from digital image
  51. warping; a growing branch of image processing.  Digital image warping deals
  52. with the geometric transformation of digital images, redefining the spatial
  53. relationship between points in an image.  One of the most common applications
  54. for image warping is texture mapping, a technique that is central to morphing.  To do a
  55. morph, the animator needs to define a correspondence between the initial and
  56. final images.  This can be done using points, triangles or meshes.  Once the
  57. relationship has been defined, the textures in the images are blended from
  58. the initial image to the final image to produce the morphing sequence.
  59.  
  60.     The method of subdividing the images varies between different morphing 
  61. programs.  The one used in this project defines common points in the two
  62. images.  For a human face, these points could include the eyes, eyebrows,
  63. nose and mouth.  Triangles are built from these points to create corresponding
  64. areas on the images.  One of the most popular triangulation algorithms,
  65. Delaunay triangulation is used in this program.  Delaunay's algorithm
  66. maximizes the angles within each triangle and minimizes the lengths of the
  67. sides.
  68.  
  69.     After subdividing the images, the transformation from the source to the 
  70. destination begins.  
  71.  
  72.  
  73.  
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94. Project Description
  95.     
  96. A. Operating Environment
  97.  
  98. 1.    DOS 5.0 or above
  99. 1.      80386 or above
  100. 2.      VGA 320x200 256 color
  101. 3.      Mouse & MS Mouse Driver ver 8.0 or above
  102. 4.      At least 5M hard disk space for output files
  103. 5.    At least 300K conventional memory
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117. B. Program Description
  118.  
  119. 1. Menu Display
  120.  
  121. a. Input image files
  122.  
  123.     Two buttons named "Source" and "Target" are used to 
  124. input images file.  When the button "Source" is clicked, a dialog box
  125. would appear and prompt the user to input the source file.  When 
  126. this file is successfully loaded, the button name is replaced by the 
  127. source file name and the image would appear on the left window of the
  128. menu.  Similarly, the destination file can be loaded using the "Target"
  129. button.  The destination image would appear on the right window of
  130. the menu.
  131.  
  132. b. image Movement
  133.     
  134.         As the window size is smaller than the image size,
  135. clipping is employed to display only a portion of the image in the
  136. screen.  In order to scroll to the other part of the images, four
  137. buttons can be used.  These four buttons placed at the lower left 
  138. part of the menu.  The four direction buttons represent the 
  139. movement in the four directions.  Two speed can be used to move.  
  140. When the center part of button is clicked, the movement is slow.  
  141. However, when the tip of the direction sign is clicked, the 
  142. movement is about five times the slower one. 
  143.  
  144. c. Mouse Pointer
  145.  
  146.     A mouse pointer can be seen in the menu.  It is used not 
  147. only to click the menu button, but also for point selection.  When
  148. click the mouse on the images, a white spot appeared indicating
  149. that that point is chosen.
  150.  
  151. d. Add Button
  152.  
  153.         The Add button is used to confirm the points selected on the
  154. images.  After the selecting the two points on each image, the user
  155. should then click the Add button to confirm that this point is to be 
  156. added.  After clicking this button, the point would be read and 
  157. triangles are formed on the images.
  158.  
  159. e. Morph Button
  160.  
  161.         The button Morph is used to start morphing.  When this button
  162. is clicked, a dialog box would ask the user to input the file name.
  163. It should be not more than five characters since another three digits
  164. would added to the end of the file name to indicate the series of images.
  165. Then, another dialog box would prompt the user to input the number of
  166. intermediate steps required.
  167.  
  168. f. Exit Button
  169.     This button is clicked when the user would like to 
  170. terminate the execution of the program.
  171.  
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
  179.  
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186. C. Program Processing
  187.  
  188. 1. Delaunay Triangulation 
  189.  
  190.     The system use the "On-line Delaunay Triangulation" 
  191. algorithm to link up all inputted points on the source and destination
  192. images.  On-line algorithm is used to give user a look
  193. on the triangulation before input another points.
  194.  
  195.     The employ of the optimal triangulation algorithm is to 
  196. avoid generating triangles with sharp angles and long edges.  This 
  197. is important for image processing applications as it ensures that 
  198. only nearby data points will be used in the surface patch 
  199. computations that will follow.
  200.  
  201.     Initially, the four corners are pre-inputted as the first four 
  202. points.  Therefore, a diagonal line is seen on each images after
  203. loading since two triangles are formed by four corner points.  In 
  204. addition, no points can be added on the four boundary edges of 
  205. each images.
  206.  
  207. 2. Bresenham Scan Converting Line Algorithm
  208.  
  209.     Bresenham Scan Converting Line Algorithm is used to 
  210. draw lines on the images.  All the triangles are drawn by this line
  211. drawing method.
  212.  
  213. 3. Linear Transformation
  214.  
  215.         When the program starts to morph, the transformation of the
  216. triangles is done by Linear Transformation.  This algorithm provides
  217. an easy way to find the intermediate position of the triangles.
  218.  
  219. 4. Find Points Within Particular Triangles
  220.  
  221.     After finding the intermediate triangles, corresponding 
  222. points of the source, intermediate and target triangles must be 
  223. known in order to find the corresponding color for those points.
  224.  
  225.     A similar approach to the scan converting left edge of a 
  226. polygon described in textbook is used to find out all the points 
  227. within a given triangle.
  228.  
  229. 5. Affine Transformation
  230.  
  231.     After finding the points in each triangles, Affine 
  232. Transformation is used to find its corresponding points in the 
  233. source and target images
  234.  
  235. 6. Finding Color
  236.  
  237.     For each pixels, its color is then calculated from the source 
  238. and target images' color and approximate color is displayed.
  239.  
  240. 7. Program Output
  241.  
  242.     The intermediate steps are shown in the screen.  In addition, all the 
  243. intermediate images would be stored on disk with the user given file
  244. names.  The file format is 320x200 GIF.
  245.  
  246.  
  247.  
  248.  
  249.  
  250.  
  251.  
  252.  
  253.  
  254.  
  255. D. Other Consideration and Limitation
  256.  
  257. 1. Color (8-bit color VS 24-bit color)
  258.  
  259.         Due to the limitation of the memory of DOS, it is difficult to
  260. allocate sufficient memory to store the 24-bit image during program
  261. processing.  Hence, 8-bit 256 color is chosen.
  262.  
  263.  
  264. 2. Performance in Time
  265.  
  266.     After integrating the whole program, system testing began.  We 
  267. found that most of the time is spent in calculating the color of each pixel.  
  268. Since at that time, each pixel is required to scan the whole color palette 
  269. and find the closest color.  That is, each pixel for each image must scan
  270. an 256-sized array.  The performance on this is bad.
  271.  
  272.     Therefore, two methods are employed to solve this problem.  
  273. Firstly, we changed that part of code into assembly language in order to 
  274. make it behave better.  This makes the program run in a much faster.  But 
  275. it is still slow. Then, we change our finding color strategy.  A 32x32x32 
  276. hash table representing 64x64x64 RGB color is created to store the closest 
  277. color index in the palette table at the time of morphing.  In finding the 
  278. 6x6x6-bits color from 5x5x5 bits color,  the least significant bit is ignored.  
  279. This approximate quite good and give a better performance in time.
  280.  
  281. 4. Limitation in Transformation
  282.  
  283.     The transformation is mainly divided into two parts.  The reason 
  284. for this is due to the two different color palette for two different images
  285. and also different triangles formed on the two images.
  286.  
  287.     For the first half of the morphing, the color palette of the source 
  288. images would be used while for the second half, the color palette of the
  289. target images is used.  This makes the output has a visible change in the
  290. color just before and after the switching of the color palette.
  291.  
  292.     Since the positions of the corresponding points for the source and 
  293. target images might different a lot, the triangles formed might be
  294. completely different for two images.  Hence, we cannot just use the
  295. displayed formed of triangles to morph images.  The method is that, for
  296. the first half series, the triangles formed by Delaunay Triangulation of the 
  297. source images is used to morph with the corresponding triangles2 of the
  298. target images.  Similarly, the triangles formed by Delaunay Triangulation
  299. of the target image are used to morph with the corresponding triangles of
  300. the source images.  Due to this reason, if the corresponding points of the
  301. source and target images differ a lot, some intermediate steps might
  302. appear to have some overlapping.
  303.  
  304.  
  305.  
  306.  
  307.  
  308.  
  309.  
  310.  
  311.  
  312.  
  313.  
  314.  
  315.  
  316.  
  317.  
  318.  
  319.  
  320.  
  321.  
  322.  
  323.  
  324. Bibilography
  325.  
  326. 1.      Wolberg, Georage.  Digital Image Warping.  IEEE Computer Society
  327. Press, 1990.
  328.  
  329. 2.      L. De Floriani and E. Puppo.  An On-line Algorithm for Constrained
  330. Delaunat Triangulation.  CVGIP: Graphical Models And Image Processing,
  331. Vol 54, No. 3, July, pp. 290-300, 1992
  332.  
  333. 3.      Detlef Ruprecht and Heinrich Muller.  Image Warping with Scattered
  334. Data Interpolation Methods.  Forschungbericht Nr. 443. 6 November 1992
  335.  
  336. 4.      Valerie Hall.  Introduction to Morphing.  July, 1992.
  337.  
  338. 5.      Foley, van Dam, Feiner and Hughes.  Computer Graphics: Principles
  339. and Practice. 2nd Edition, Addision Wesley
  340.  
  341.  
  342.  
  343.